<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="initial-scale=1, maximum-scale=1, user-scalable=0, viewport-fit=cover" />
	<title>binary-tree</title>
</head>
<body>
<img width="1000" src="./binaryTree.png" alt="">
<script>

class Node {
	constructor(value) {
		if (Object.prototype.toString.call(value) !== '[object Number]') throw new Error('value 需要是一个数字')
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

class BinaryTree {
	constructor(value) {
		this.root = typeof value === 'number' ? new Node(value) : null;
	}

	addNode(value) {
		const newNode = new Node(value);
		if (!this.root) {
			this.root = newNode
		}
		else {
			this._insertNode(this.root, newNode)
		}

		return newNode;
	}


	_insertNode(head = this.root, node) {
		// 向左
		if (head.value > node.value) {
			if (head.left) {
				this._insertNode(head.left, node);
			}
			else {
				head.left = node;
			}
		}
		// 向右
		else if (head.value < node.value) {
			if (head.right) {
				this._insertNode(head.right, node);
			}
			else {
				head.right = node;
			}
		}
	}

	getMinNode(currentNode = this.root) {
		// if (!this.root) return null;
		// let currentNode = this.root;
		while (currentNode.left) {
			currentNode = currentNode.left;
		}
		return currentNode;
	}

	getMaxNode(currentNode = this.root) {
		// if (!this.root) return null;
		// let currentNode = this.root;
		while (currentNode.right) {
			currentNode = currentNode.right;
		}
		return currentNode;
	}

	findNode(value) {
		if (!this.root) return null;
		return this._find(this.root, value)
	}

	_find(head = this.root, value) {
		// 命中
		if (head.value === value) {
			return head;
		}
		// 向左
		else if (head.value > value) {
			if (!head.left) {
				return null;
			}
			else {
				return this._find(head.left, value)
			}
		}
		// 向右
		else if (head.value < value) {
			if (!head.right) {
				return null;
			}
			else {
				return this._find(head.right, value)
			}
		}
	}

	removeNode(value) {
		if (!this.root) return null;
		this._remove(this.root, value)
	}

	// 把传进来的节点弄利索了(节点本身 value left right) 再返回
	_remove(head = this.root, value) { // {35}  24
		if (!head) return; // 不可以传 null
		// 向左
		if (head.value > value) {
			head.left = this._remove(head.left, value) // 把变量传入后, 返回全新的变量地址 并 赋值
		}
		// 向右
		else if (head.value < value) {
			head.right = this._remove(head.right, value) // 同上
		}
		//  命中
		else if (head.value === value) {
			// 双无
			if (!head.left && !head.right) {
				head = null;
			}
			// 仅左有
			else if (head.left && !head.right) {
				head = head.left;
			}
			// 仅右有
			else if (!head.left && head.right) {
				head = head.right;
			}
			// 双有( 重点, 难点 ), 程序偏向于找右侧最近的值( 也是 右侧最小的值 )
			else if (head.left && head.right) {
				const rightMinNode = this.getMinNode(head.right) // 拿到右侧最小的值的节点, 赋值给一个变量
				head.value = rightMinNode.value; // 将要被删除变量的值 改变为 右侧最小的值的节点的值 ( 目前二叉树中有两个相同的值 )
				head.right = this._remove(head.right, rightMinNode.value) // 把要删除的节点的右支重新处理一边, 并重新赋值给右支
			}
		}
		return head;
	}

	getHeight(currentNode = this.root) {
		if (!currentNode) return 0; // 处理边界
		let height = 1;
		const callNodeList = [currentNode, null]; // [ ]
		let firstNode;
		while ((firstNode = callNodeList.shift()) !== undefined) {
			if (!firstNode) {
				if (callNodeList.length) {
					++height;
					callNodeList.push(null)
				}
				else {
					return height;
				}
				continue;
			}
			firstNode.left && callNodeList.push(firstNode.left)
			firstNode.right && callNodeList.push(firstNode.right)
		}
	}
}

const newBinaryTree = new BinaryTree(35)

newBinaryTree.addNode(24)
newBinaryTree.addNode(50)
newBinaryTree.addNode(18)
newBinaryTree.addNode(28)
newBinaryTree.addNode(90)
newBinaryTree.addNode(15)
newBinaryTree.addNode(23)
newBinaryTree.addNode(26)
newBinaryTree.addNode(86)
newBinaryTree.addNode(95)
newBinaryTree.addNode(88)
newBinaryTree.addNode(98)
newBinaryTree.addNode(89)

// console.log(`newBinaryTree.getMinNode--`, newBinaryTree.getMinNode())
// console.log(`newBinaryTree.getMaxNode--`, newBinaryTree.getMaxNode())
// console.log(`newBinaryTree.findNode---`, newBinaryTree.findNode(90))
// newBinaryTree.removeNode(24)

console.log(`newBinaryTree.getHeight---`, newBinaryTree.getHeight())

console.log(`newBinaryTree---`, newBinaryTree)
</script>
</body>
</html>
